package com.sjy.bloomFilter;

import com.sjy.utils.MurmurHash3;
import lombok.Getter;
import lombok.Setter;

import java.nio.charset.StandardCharsets;
import java.util.BitSet;
import java.util.Objects;

/**
 * @program: BlomFilter
 * @description:
 * @author: 智慧的苏苏
 * @create: 2025-09-02 15:16
 **/
@Getter
@Setter
public class BloomFilter {
    private final int bitSize;
    private final int hashCount;
    private final BitSet bitSet;

    public BloomFilter(int expectedInsertions, double fpp) {
        if (expectedInsertions <= 0) {
            throw new IllegalArgumentException("expectedInsertions must be greater than 0");
        }
        if (fpp <= 0 || fpp >= 1) throw new IllegalArgumentException("fpp must be between 0 and 1");
        this.bitSize = optimalNumOfBits(expectedInsertions, fpp);
        this.hashCount = optimalNumOfHashFunctions(expectedInsertions, bitSize);
        this.bitSet = new BitSet(bitSize);
    }

    public BloomFilter add(Object element) {
        Objects.requireNonNull(element);
        byte[] bytes = element.toString().getBytes(StandardCharsets.UTF_8);
        long hash64 = MurmurHash3.hash64(bytes);
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 32);

        for (int i = 0; i < hashCount; i++) {
            int combinedHash = hash1 + i * hash2;
            if (combinedHash < 0) combinedHash = ~combinedHash;
            int pos = combinedHash % bitSize;
            bitSet.set(pos);
        }
        return this;
    }

    /**
     * 判断元素是否可能存在
     */
    public boolean isExist(Object element) {
        Objects.requireNonNull(element);
        byte[] bytes = element.toString().getBytes(StandardCharsets.UTF_8);
        long hash64 = MurmurHash3.hash64(bytes);
        int hash1 = (int) hash64;
        int hash2 = (int) (hash64 >>> 32);

        for (int i = 0; i < hashCount; i++) {
            int combinedHash = hash1 + i * hash2;
            if (combinedHash < 0) combinedHash = ~combinedHash;
            int pos = combinedHash % bitSize;
            if (!bitSet.get(pos)) {
                return false;
            }
        }
        return true;
    }

    private static int optimalNumOfBits(long n, double p) {
        return (int) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));
    }


    private static int optimalNumOfHashFunctions(long n, long m) {
        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));
    }


}
